1310. Наибольший блок

 

 Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.

Вычислить длину наибольшего блока заданной строки S.

 

Вход.  Единственная строка S (|S| ≤ 106).

 

Выход. Длина наибольшего блока строки S.

 

Пример входа

abaabaab

 

Пример выхода

5

 

 

РЕШЕНИЕ

строки – z-функция

 

Анализ алгоритма

Построим для строки S в массиве v z-функцию. Найдем и выведем длину ее наибольшего блока.

 

Реализация алгоритма

Входная строка s содержит не более 1000000 символов. z-функцию строки s сохраняем в векторе v.

 

vector<int> v;

char s[1000010];

 

Функция z строит и возвращает z-функцию для строки s.

 

vector<int> z(char *s)

{

  int i, l, r;

  vector<int> z(len, 0);

  for (i = 1, l = 0, r = 0; i < len; i++)

  {

    if (i <= r) z[i] = min (r - i + 1, z[i - l]);

    while (i + z[i] < len && s[z[i]] == s[i + z[i]]) z[i]++;

    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;

  }

  return z;

}

 

Читаем входную строку s, вычисляем ее длину len. Строим z-функцию при помощи функции z. Находим длину res наибольшего блока строки s и выводим ее.

 

gets(s); len = strlen(s);

v = z(s); res = 0;

for(i = 1; i < len; i++)

  if (res < v[i]) res = v[i];

printf("%d\n",res);